<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>318. 最大单词长度乘积</title>
  </head>
  <body>
    <script>
      //       给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

      // 示例 1：

      // 输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
      // 输出：16
      // 解释：这两个单词为 "abcw", "xtfn"。
      // 示例 2：

      // 输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
      // 输出：4
      // 解释：这两个单词为 "ab", "cd"。
      // 示例 3：

      // 输入：words = ["a","aa","aaa","aaaa"]
      // 输出：0
      // 解释：不存在这样的两个单词。

      // 提示：

      // 2 <= words.length <= 1000
      // 1 <= words[i].length <= 1000
      // words[i] 仅包含小写字母
      /**
       * @param {string[]} words
       * @return {number}
       */
      var maxProduct = function (words) {
        // 通过charCode获取字母与a的差值数字
        var getCharCodeDiff = function (char) {
          return char.charCodeAt(0) - 'a'.charCodeAt(0)
        }

        var n = words.length,
          lens = [],
          masks = []
        for (var i = 0; i < n; i++) {
          // 存储单词长度
          var len = words[i].length
          lens.push(len)
          // 将单词转换为二进制掩码存储
          var mask = 0
          for (var j = 0; j < len; j++) {
            mask |= 1 << getCharCodeDiff(words[i][j])
          }
          masks.push(mask)
        }
        // 两层遍历挨个比较最大乘积
        var max = 0
        for (var i = 0; i < n; i++) {
          for (var j = i + 1; j < n; j++) {
            // 通过逻辑与计算两个二进制数是否存在相同位
            if ((masks[i] & masks[j]) == 0) {
              max = Math.max(max, lens[i] * lens[j])
            }
          }
        }

        return max
      }
    </script>
  </body>
</html>
